package bTree;

public class MyBTree {
    class BTreeNode{
        int[] key;
        int usedSize;
        BTreeNode parent;
        BTreeNode[] children;
        public BTreeNode(){
            key = new int[M];
            children = new BTreeNode[M + 1];
        }
    }
    private final int M = 3;
    //根节点
    BTreeNode root;

    public boolean add(int val){
        BTreeNode cur = root;
        if(cur == null){
            BTreeNode node = new BTreeNode();
            node.key[0] = val;
            node.usedSize++;
            root = node;
            return true;
        }
        BTreeNode parent = new BTreeNode();
        //1.寻找插入节点
        while (cur != null){
            int i = 0;
            for(;i < cur.usedSize;i++){
                if(val == cur.key[i]){
                    //说明已经插入过这个数据
                    return false;
                }else if(val < cur.key[i]){
                    break;
                }
            }
            parent = cur;
            cur = cur.children[i];
        }

        // 寻找插入位置 2.进行插入
        //插入排序
        int i = parent.usedSize - 1;
        for(;i >= 0;i--){
            if(val < parent.key[i]){
                parent.key[i+1] = parent.key[i];
            }else {
                break;
            }
        }
        parent.key[i+1] = val;
        parent.usedSize++;
        if(parent.usedSize >= M){
            //进行分裂
            split(parent);
        }
        return true;
    }

    private void split(BTreeNode cur) {
        BTreeNode parent = cur.parent;
        //1.将cur结点中一半数据分给新创建的节点
        BTreeNode newNode = new BTreeNode();
        int mid = cur.usedSize / 2;
        int index = mid+1;
        int i = 0;
        for(;index < M;index++,i++){
            newNode.key[i] = cur.key[index];
            newNode.usedSize++;
            newNode.children[i] = cur.children[index];
            cur.children[index] = null;
            cur.usedSize--;
        }
        newNode.children[i] = cur.children[index];
        cur.children[index] = null;
        if(cur == root){
            parent = new BTreeNode();
            root = parent;
            root.key[0] = cur.key[mid];
            root.usedSize++;
            cur.usedSize--;
            root.children[0] = cur;
            root.children[1] = newNode;
            cur.parent = root;
            newNode.parent = root;
            return;
        }
        newNode.parent = parent;

        //2.将cur节点中间数据提取到父节点当中去
        int x = parent.usedSize - 1;
        for(;x >= 0;x--){
            if(parent.key[x] > cur.key[mid]){
                parent.key[x+1] = parent.key[x];
                parent.children[x+2] = parent.children[x+1];
            }else{
                break;
            }
        }

        parent.key[x+1] = cur.key[mid];
        cur.usedSize--;parent.usedSize++;
        parent.children[x+1] = cur;
        parent.children[x+2] = newNode;

        //检查父亲节点情况
        if(parent.usedSize >= M){
            split(parent);
        }
    }
    public void inorder(BTreeNode root){
        if(root == null)
            return;
        for(int i = 0; i < root.usedSize; ++i){
            inorder(root.children[i]);
            System.out.println(root.key[i]);
        }
        inorder(root.children[root.usedSize]);
    }
}
